/**
 * 
 */
package ar.uba.fi.tonyvaliente.tree;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Iterator;
import java.util.List;
import java.util.logging.Logger;

import sun.rmi.runtime.Log;

/**
 * @author santiago
 *
 */
public class InnerBPlusTreeNode<K extends Comparable<K>, V> extends BPlusTreeNode<K, V> {

	private static Logger log = Logger.getLogger(InnerBPlusTreeNode.class.getName());

	/**
	 * Lista de referencias a los nodos hijos.
	 * Van en paralelos con las claves.
	 * La referencia 0 se corresponde con el hijo izquierdo de la clave 0,
	 * la referencia 1 se corresponde con el hijo derecho de la clave 0,
	 * la referencia 1 se corresponde con el hijo izquierdo de la clave 1,
	 * La referencia 2 se corresponde con el hijo derecho de la clave 1, etc.
	 */
	private List<Reference<K, V>> references = new ArrayList<Reference<K,V>>();
	
	/**
	 * Lista de claves del nodo.
	 * @see references 
	 */
	private List<K> keys = new ArrayList<K>();
	
	protected InnerBPlusTreeNode(Reference<K, V> parent) {
		super(parent);
		this.cantidadElementos = 0;
	}

	protected InnerBPlusTreeNode( BPlusTree<K, V> tree) {
		super(tree);
		this.cantidadElementos = 0;
	}
	
	protected InnerBPlusTreeNode( BPlusTree<K, V> tree, Integer elementosPorNodo) {
		super(tree);
		this.maxCantidadElementos = elementosPorNodo;
		this.cantidadElementos = 0;
	}
	
	protected InnerBPlusTreeNode(Reference<K, V> parent, BPlusTree<K, V> tree,
			Integer maxCantidadElementos) {
		super(parent, tree, maxCantidadElementos);
		this.cantidadElementos = 0;
		
	}
	
	protected boolean isInner() {
		return true;
	}

	protected boolean isLeaf() {
		return false;
	}

	@Override
	protected AddResult<K, V> add(K key, V value) throws BPlusTreeException {

		boolean modify = false;
		int keyIndex = getKeyIndex(key);
		
		Reference<K, V> reference = null;
		
		K clave = null;
		
		if (keys.size() > 0) {
			clave = keys.get(keyIndex);
		} else {
			// No se hace nada, si la lista está vacia no hay clave.
			log.fine("lista de claves vacia");
		}
		
		// Si hay una clave para nuestro elemento.
		// Lo buscamos en el nodo correspondiente.
		if(clave != null){
			if(key.compareTo(clave) >= 0){
				reference = references.get(++keyIndex);
			}else{
				reference = references.get(keyIndex);
			}
			
		}else{
			
			modify = true;
			
			reference = tree.createReference();
			
			LeafBPlusTreeNode<K, V> node = new LeafBPlusTreeNode<K, V>(this.getThisReference(), tree, tree.getElementosPorNodo());
			
			Reference<K, V> leftReference = tree.createReference();
			LeafBPlusTreeNode<K, V> leftNode = new LeafBPlusTreeNode<K, V>(this.getThisReference(), tree, tree.getElementosPorNodo());
			leftReference.setNode(leftNode);
			
			node.setPrevious(leftReference);
			node.setNext(null);
			
			reference.setNode(node);
			
			leftNode.setPrevious(null);
			leftNode.setNext(reference);
			
			tree.getDirtyNodes().add(reference);
			tree.getDirtyNodes().add(leftReference);
			
			keys.add(key);
			references.add(0, leftReference);
			references.add(1, reference);
			
			this.getTree().setFirst(leftReference);
			
			this.cantidadElementos++;
			
		}
		
		BPlusTreeNode<K, V> node = reference.getNode();
		reference.getNode().setParent(this.getThisReference());
		
		node.setTree(this.tree);
		
		AddResult<K, V> result = node.add(key, value);
		
		if(result != null){
			
			modify = true;
			
			K resultKey = result.getKey();
			int resultKeyIndex = this.getKeyIndex(resultKey);
			this.keys.add(resultKeyIndex, resultKey);
			Collections.sort(keys);
			int posicionClave = keys.indexOf(result.getKey());
			references.remove(reference);
			references.add(posicionClave, result.getLeftReference());
			references.add(++posicionClave, result.getRightReference());
			this.cantidadElementos++;
			
			if( cantidadElementos.compareTo(this.getTree().getElementosPorNodo()) > 0){
				modify = false;
				result = this.split();
				
				
			}else{
				result = null;
			}
		}
		
		this.getThisReference().setNode(this);
		if(modify){
			tree.getDirtyNodes().add(this.getThisReference());
		}
		
		return result;
	}

	/**
	 * Obtenemos la posición de la clave
	 * @param key
	 * @return
	 */
	private int getKeyIndex(K key) throws BPlusTreeException {
		
		//int keyIndex = this.keys.indexOf(key);
		int keyIndex = -1;
		
		//Collections.sort(keys);
		//keyIndex = Collections.binarySearch(keys, key);
		//log.info("keyIndex de binary search: " + keyIndex);
		
		if(keys.size() > 0){
			Iterator<K> it = keys.iterator();
			
			Boolean found = false;
			// Buscamos la primera clave mayor o igual al elemento a insertar.
			// Si todas las claves son menores devolvemos la posición
			// de la última clave.
			while (it.hasNext() && !found) {
				K clave = it.next();
				keyIndex++;
				if(clave.compareTo(key) >= 0){
					found = true;
				}
			}
		}else{
			keyIndex = 0;
		}
		return keyIndex;
	}

	@Override
	protected V get(K key) throws BPlusTreeException {

		V returnValue = null;
		int keyIndex = getKeyIndex(key);
		
		K clave = null;
		
		try{
			clave = keys.get(keyIndex);
		}catch(IndexOutOfBoundsException e){
			// No se hace nada, si la lista está vacia no hay clave.
			log.fine("lista de claves vacia");
		}
		
		if(clave != null){
			if(key.compareTo(clave) < 0){
				returnValue = this.getReferences().get(keyIndex).getNode().get(key);
			}else{
				returnValue = this.getReferences().get(keyIndex + 1).getNode().get(key);
			}
		}
		
		return returnValue;
	}

	private AddResult<K, V> split() throws BPlusTreeException {

		Reference<K, V> leftReference = this.getThisReference();
		
		Reference<K, V> rightReference = this.getTree().createReference();
		InnerBPlusTreeNode<K, V> rightNode = new InnerBPlusTreeNode<K, V>(this.getParent(), this.getTree(), this.getMaxCantidadElementos());
		List<K> rightKeys = new ArrayList<K>();
		List<Reference<K, V>> rightReferences = new ArrayList<Reference<K, V>>();
		
		rightReference.setNode(rightNode);
		rightNode.setKeys(rightKeys);
		rightNode.setReferences(rightReferences);
		
		// Tomamos el valor medio
		int medio = this.getCantidadElementos()/2;
		
		// Obtenemos la clave media, esta será la clave a promover.
		K claveMedia = keys.get(medio);
		
		// Copiamos los valores a los nuevos nodos.
		int i = 0;
		while (i < keys.size()) {
			K key = keys.get(i);

			if(key.compareTo(claveMedia) >= 0){
				this.keys.remove(key);
				if (key.compareTo(claveMedia) > 0) {
					rightKeys.add(key);
				}
			}
			
			
			if (i < medio) {
				i++;
			} else {
				Reference<K, V> tempRef = this.references.get(i+1);
				tempRef.getNode().setParent(rightReference);
				rightReferences.add(tempRef);
				this.references.remove(i+1);
			}
		}

		this.setCantidadElementos(this.getKeys().size());
		rightNode.setCantidadElementos(rightKeys.size());
		
		AddResult<K, V> resultado = new AddResult<K, V>();
		resultado.setLeftReference(leftReference);
		resultado.setRightReference(rightReference);
		resultado.setKey(claveMedia);
		
		tree.getDirtyNodes().add(leftReference);
		tree.getDirtyNodes().add(rightReference);
		
		return resultado;
	}
	
	protected List<Reference<K, V>> getReferences() {
		return references;
	}

	protected void setReferences(List<Reference<K, V>> references) {
		this.references = references;
	}

	protected List<K> getKeys() {
		return keys;
	}

	protected void setKeys(List<K> keys) {
		this.keys = keys;
	}
	
	@Override
	public String toString() {
		return this.keys.toString() + " " + this.references.toString();
	}

	
}
